package leecode

func lenLongestFibSubseq(arr []int) int {
	hashMap := make(map[int]int) //记录数组中的元素出现的位置
	size := len(arr)
	for i := 0; i < size; i++ {
		hashMap[arr[i]] = i
	}
	dp := make([][]int, size)
	for i := 0; i < size; i++ {
		dp[i] = make([]int, size)
	}
	var result int
	for i := 0; i < size-1; i++ {
		for j := i + 1; j < size; j++ {
			dp[i][j] = 2
			diff := arr[j] - arr[i]
			if index, ok := hashMap[diff]; ok && index < i {
				if dp[index][i] == 0 {
					dp[i][j] = 3
				} else {
					dp[i][j] = dp[index][i] + 1
				}
				result = max(result, dp[i][j])
			}
		}
	}
	return result
}
